package solutionsdemo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2024-01-29
 * Time: 19:31
 */

/**
 * 通过 前序遍历 和 中序遍历 创建生成二叉树
 */
public class BuildTree {
    /**
     * @param preorder 前序遍历数组  用来查找根节点(preIndex)
     * @param inorder  中序遍历赎罪  用来判断左右子树(通过inBegan,inEnd)
     * @return
     */
    public int preIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,preorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegan,int inEnd) {
        if(inBegan > inEnd) {
            return null;
        }
        //新建一颗根节点(在preorder中)
        TreeNode root = new TreeNode(preorder[preIndex]);
        preIndex++;
        //查找 根节点在中序遍历的位置
        int rootIndex = findKeyIndex(inorder,inBegan,inEnd,root.val);
        root.left = buildTreeChild(preorder,inorder,inBegan,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1, inEnd);
        return root;
    }

    private int findKeyIndex(int[] inorder, int inBegan, int inEnd,int val) {
        for(int i = inBegan; i <= inEnd; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}